<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 封装单向链表类
      function LinkedList() {
        // 内部的类：节点类
        function Node(data) {
          this.data = data
          this.next = null // 指向下一节点的引用默认为null
        }

        // 属性
        this.head = null // 链表头部
        this.length = 0 // 记录链表的长度

        // 方法
        // 1.append 追加方法
        LinkedList.prototype.append = function (data) {
          // 1.创建新的节点
          var newNode = new Node(data)

          // 2.判断是否添加的是第一个节点
          if (this.length === 0) {
            // 2.1是第一个节点
            this.head = newNode
          } else {
            // 2.2不是第一个节点
            // 找到最后一个节点
            // 判断current是否为空，为空即为链表最后一个节点，停止循环
            var current = this.head // 此时this.head指向最后一个节点
            while (current.next) {
              current = current.next
            }

            // 让最后节点的next指向新添加的节点
            current.next = newNode
          }

          // 3.链表长度增加1
          this.length += 1
        }

        // 2.toString
        LinkedList.prototype.toString = function () {
          // 1.定义变量
          var current = this.head
          var listString = ''

          // 2.循环获取一个个的节点
          while (current) {
            listString += current.data + ' '
            current = current.next
          }

          return listString
        }

        // 3.insert(position,data) 插入 参数：传入位置和数据
        LinkedList.prototype.insert = function (position, data) {
          // 1.对 position 进行越界判断 不能为负数且不能超过链表长度
          if (position < 0 || position > this.length) return fasle

          // 2.根据data创建newNode
          var newNode = new Node(data)

          // 3.判断插入的位置是否是第一个
          if (position === 0) {
            newNode.next = this.head // 先让newNode指向原第一个
            this.head = newNode // 再让this.head指向插入的
          } else {
            var index = 0
            var current = this.head
            var previous = null
            // 当index小于position就一直往后找
            while (index++ < position) {
              previous = current
              current = current.next
            }

            newNode.next = current
            previous.next = newNode
          }

          // 4.链表长度增加1
          this.length += 1

          return true
        }

        // 4.get(position) 获取对应位置的元素
        LinkedList.prototype.get = function (position) {
          // 1.越界判断
          if (position < 0 || position >= this.length) return null

          // 2.获取对应的数据
          var current = this.head
          var index = 0
          while (index++ < position) {
            current = current.next
          }

          return current.data
        }

        // 5.indexOf(element)返回元素在列表的索引，如果没有则返回-1
        LinkedList.prototype.indexOf = function (data) {
          // 1.定义变量
          var current = this.head
          var index = 0

          // 2.开始查找
          while (current) {
            if (current.data === data) {
              return index
            }
            current = current.next
            index += 1
          }

          // 3.没有找到
          return -1
        }

        // 6.update(positon,element)
        LinkedList.prototype.update = function (position, newData) {
          // 1.越界判断
          if (position < 0 || position >= this.length) return null

          // 2.查找正确的节点
          var current = this.head
          var index = 0
          while (index++ < position) {
            current = current.next
          }

          // 3.将positon位置的node的data修改为新newDate
          current.data = newData
          return true
        }

        // 7.removeAt(positon)
        LinkedList.prototype.removeAt = function (position) {
          // 1.越界判断
          if (position < 0 || position >= this.length) return null

          var current = this.head
          // 2.判断删除的是否是第一个节点
          if (position === 0) {
            this.head = this.head.next
          } else {
            var index = 0
            var previous = this.head
            while (index++ < position) {
              previous = current
              current = current.next
            }
            // 让前一个节点的next指向current的next
            previous.next = current.next
          }

          // 3.长度减小 -1
          this.length -= 1
          return current.data
        }

        // 9.remove(element)
        LinkedList.prototype.remove = function (data) {
          // 1.获取data在链表中的位置
          var position = this.indexOf(data)

          // 2.根据位置信息删除节点
          return this.removeAt(position)
        }

        // 10.isEmpty()
        LinkedList.prototype.isEmpty = function () {
          return this.length
        }
        // 11.size()
        LinkedList.prototype.size = function () {
          return this.length
        }
      }

      // 测试代码
      var list = new LinkedList()
      list.append('a')
      list.append('b')
      list.append('c')
    </script>
  </body>
</html>
